The present invention relates to an image processing apparatus, an image processing method and an image processing program, particularly to an image processing apparatus, an image processing method and an image processing program for quantizing the multi-density level image data into digital halftone output image data.
The known prior art quantization method for converting the multi-density level original image data into digital halftone image data for outputting includes a textural dither method and an error diffusion method. Of these methods, the error diffusion method provides comparatively high image quality, and is therefore often used in high-quality application. Attempts have been made for various improvements of this method. The problem with the error diffusion method related to image quality is how to reduce the texture specified to algorithm, without amplifying a noise.
For example, attempts have been made to ensure the uniformity using a plurality of error diffusion matrices (Patent Document 1). To be more specific, two matrices are switched in response to the input value. The larger one is used in highlight or shadow area to avoid occurrence of a pattern called “worm”; whereas the smaller one is used in the intermediate area to suppress noise.
To generate more uniform results in highlight or shadow area, a threshold value dependent on an output value is used to change the threshold value (see Patent Document 2). To put it more specifically, the threshold value is changed for the surrounding pixels in response to the input, depending on whether the binary output is white or black, and this is repeatedly used for propagation.
In addition to the aforementioned prior arts, attempts have also been made to change the method of optimizing the size of the error diffusion matrix and coefficient, or the sequence of processing (direction of scanning). From these techniques, a certain effect has been achieved, but is still far from satisfactory.
Apart from the aforementioned error diffusion method, its improved version or dither method, a digital-half toning technique based on anti-correlation has been proposed as a quantization method (Patent Document 1). According to this method, the sequence representing the information on dot occurrence (hereinafter referred to as “dot occurrence pattern”) is set for each pixel, or in other words, the sequence of dot presence/absence information items in the number substantially proportional to the number of gradations constituting the relevant pixel is set for each pixel. Based on this sequence, halftoning processing is applied. In determining the contents of the dot occurrence pattern of the relevant pixel, the dot occurrence pattern already determined for the surrounding pixels is used. The expected value for the occurrence of dots in the surrounding pixels (hereinafter referred to as “histogram”) is calculated for each of the element numbers of the elements constituting these dot occurrence patterns. According to this method, the dot occurrence pattern of the relevant dot is determined in such a way that, based on this expected value, the dot presence information is assigned to the element number having a smaller number of dot occurrences, on a priority basis, and a dot absence information is assigned to the element number having a greater number of dot occurrences.
According to the image processing art based on anti-correlation digital halftoning technique, when attention is paid to one particular pixel, the frequency of dot occurrence is proportional to the pixel value of that pixel. When attention is paid to a plurality of adjacent pixels, the dots for each pixel occur in such a way that the anti-correlation to the surrounding pixels is substantially the maximum. This arrangement improves the dispersion of the dots formed on the recording medium at the time of recording the image. Thus, the digital halftoning method based on anti-correlation is characterized in that specific textures observed few in the error diffusion method area.
[Patent Document 1] Official Gazette of Japanese Patent Tokkaihei 4-328957
[Patent Document 2] Official Gazette of Japanese Patent Tokkaihei 8-107500
[Non-Patent Document 1] Dmitri A. Gusev; “Anti-Correlation Digital Halftoning” [online], August 1998, Indiana University (searched on Jul. 1, 2003), Internet www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR513
However, when calculating the histogram in the image processing according to anti-correlation digital halftoning technique, it is necessary to carry but calculations in the number equivalent to “the number of chambers by matrix size” or more, then followed by the process of sorting. Accordingly, especially when the image has a great number of bits, a very long processing time is required. This has been the problem with this prior art.